package main

import "fmt"

/*
	给定两个整数n和k，返回范围[1,N]中所有可能的k个数的组合
	你可以按任何顺序返回答案
*/

var result = [][]int{}


func combine(n int, k int) [][]int{
	// 组合是没有顺序的，[1,2][2,1]算一种组合
	result = [][]int{}
	chosen := []int{}
	combine_helper(n,k,chosen)
	return result
}

// 定义一个combine_helper辅助计算
// temp辅助存储得到的组合，result存储最后结果
// cur为当前处理的数字
func combine_helper(n int, k int,chosen []int){
	if k==0{
		//  base case
		// 当chosen的长度为k时，将chosen结果放入result中，并返回
		// 因为temp是引用类型，不能直接传入result
		temp := make([]int,len(chosen))
		copy(temp, chosen)
		fmt.Println(temp)
		result = append(result, temp)
		return
	}else if(n>=k && n>0 &&k>0){
	//recursion case
	//	fmt.Println("n=",n,", k= ",k,"chosen=",chosen)
		//choose-explore
		//组合，从1到n中选择某一元素，选择其在或不在
		// without i
		//fmt.Println("I don't chose ",n)
		combine_helper(n-1,k,chosen)
		//with i
		//fmt.Println("I chose ",n)
		chosen = append(chosen,n)
		combine_helper(n-1,k-1,chosen)
		//un-choose
		//fmt.Println("I un-chose ",n)
		chosen = chosen[:len(chosen)-1]
	}
}



func main(){
	n,k:=1,1
	combine(n,k)
	//for i:=0;i<len(result);i++{
	//	println("--------",i)
	//	for j:=0;j<len(result[i]);j++{
	//		println(result[i][j])
	//	}
	//}
}